package advance.day05;

/**
 * 描述：
 *      一个公司的上下节关系是一棵多叉树，这个公司要举办晚会，你作为组织者已经摸清了大家的心理：
 *      一个员工的直 接上级如果到场，这个员工肯定不会来。每个员工都有一个活跃度的值，
 *      决定谁来你会给这个员工发邀请函，怎么 让舞会的气氛最活跃？返回最大的活跃值。
 * @author hl
 * @version 1.0
 * @date 2020/11/10 15:43
 */
public class MaxHappy {
    public static int maxHappy(int[][] matrix){
        //dp[i][0]是i元素不参加时的最大活跃值，dp[i][1]是i元素参加时的最大活跃值
        int[][] dp = new int[matrix.length][2];
        boolean[] visited = new boolean[dp.length];
        int root = 0;
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][0] == i) {
                root = i;
                break;
            }
        }
        process(matrix, dp, visited, root);
        return Math.max(dp[root][0], dp[root][1]);
    }
    public static void process(int[][] matrix, int[][] dp, boolean[] visited, int root){
        visited[root] = true;
        dp[root][1] = matrix[root][1];
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][0] == root && !visited[i]) {
                //帮我把dp[i][0]和dp[i][1]设置好
                process(matrix, dp, visited, i);
                dp[root][1] += dp[i][0];
                dp[root][0] += Math.max(dp[i][0], dp[i][1]);
            }
        }
    }
    public static void main(String[] args) {
        int[][] matrix = { { 1, 8 }, { 1, 9 }, { 1, 10 } };
        System.out.println(maxHappy(matrix));
    }
}
